#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
#include <iostream>
#include <string>
#include <map>
#include <stdio.h>
using namespace std;

class Solution {
public:
	vector<vector<int>> kSum(vector<int>& nums, int k, size_t beg, int target)
	{
		vector<vector<int>> ret;
		map<int, bool> used;
		if (k == 2)
		{
			for (size_t i=beg, j=nums.size()-1; i<j; )
			{
				int sum = nums[i] + nums[j];
				if (sum == target)
				{
					if (used.find(nums[i]) == used.end())
					{
						used[nums[i]] = true;
						vector<int> vec;
						vec.push_back(nums[i]);
						vec.push_back(nums[j]);
						ret.push_back(vec);
					}
					++i;
					--j;
				}
				else if (sum > target)
					--j;
				else
					++i;
			}
		}
		else
		{
			for (size_t i=beg, si=nums.size()-k; i<=si; ++i)
			{
				if ( (target > 0 && nums[i] > target) || (target < 0 && nums[i] > 0))
					break;
				if (used.find(nums[i]) != used.end())
					continue;
				used[nums[i]] = true;
				vector<vector<int>> tmp = kSum(nums, k-1, i+1, target-nums[i]);
				for (size_t j=0, sj=tmp.size(); j<sj; ++j)
				{
					vector<int>& vec = tmp[j];
					vec.insert(vec.begin(), nums[i]);
					ret.push_back(vec);
				}
			}
		}
		return ret;
	}
	vector<vector<int>> fourSum(vector<int>& nums, int target) 
	{
		vector<vector<int>> ret;
		if (nums.size() < 4)
			return ret;
		sort(nums.begin(), nums.end());
		return kSum(nums, 4, 0, target);
	}
};
/*
int main()
{
	vector<string> strs;
	strs.push_back("aaabb");
	strs.push_back("aabb");
	strs.push_back("aaaab");
	string ans = Solution().longestCommonPrefix(strs);
	cout << ans << endl;
	return 0;
}
*/